Compiler optimization has its goal transforming code to increase its performance. One important factor in optimization is scheduling operations to increase the speed of program execution by utilizing predicated and speculative operations. The present invention relates to optimizing code executed on an Explicit Parallel Instruction Computing (EPIC) architecture with full predication and speculation support and performs the global task of detecting and refining potential parallelism of the source code being compiled.
The present compiler transforms the source-code program represented as a set of Basic Blocks into Extended Scalar Blocks (ESBs) by applying a compiler technique called if-conversion. Extended Scalar Blocks are regions of the predicated code where all dependencies between operations are represented explicitly as a relation between two operations for a considerable number of operations. For each ESB the compiler works out the critical path, which is defined as a sequence of operations that will take the longest CPU time and cannot be executed in parallel because of dependencies.
According to one aspect of the present invention, a condition resolving instruction is removed from the critical path so that the path of longest execution time will be dependent on resolving a condition determined by other operations not on the critical path.
According to another aspect of the invention, the condition resolving instruction is followed by a merge operation which selects between input results based on the resolution of the condition (Boolean T or F). The merge outputs the selected result to a successor operation. An xe2x80x9cunzippingxe2x80x9d procedure duplicates the successor operation and schedules the duplicate successor operations prior to the merge. The input results are provided directly to the duplicate successor operations.
According to another aspect of the invention, the outputs of duplicate successor operations are provided as inputs to the merge. Thus, during execution the duplicate successor operations will be executed in parallel while the condition is being resolved. The outputs of duplicate successor operations will be ready when the condition is resolved and the merge will select between these outputs. The xe2x80x9cunzippingxe2x80x9d operation will remove the condition resolving instruction from the critical path if the combined time of execution of both the predecessor and successor operations exceeds the time of execution of the condition resolving instruction.
According to another aspect of the invention, in the case where a second successor operation, not on the critical path, receives an output from the merge,the merge is duplicated and scheduled in parallel with the duplicate successor operations. The output of the duplicate merge operation is provided to the second successor operation.
Another aspect of the invention is using critical path strategy on a predicated representation of a program based on speculative operation mode and full predicated operation mode and implementing optimizing transformations that take into account predicate dependences and data flow dependencies.
Other advantages and features of the invention will be apparent in view of the following detailed description and appended drawings.